1819C - The Fox and the Complete Tree Traversal - CodeForces Solution

# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n; 
vector <int> g[N];
int y, maxl;
int siz[N],dfn[N],dfntot = 0;
int L,R;
bool Ok = 1;
vector <int> S[N];
vector <int> Link;
int p[N];
void dfs(int x,int fa,int dep,bool xg = 0)
{
	if(dep > maxl) y = x, maxl = dep; 
	if(xg) siz[x] = 1,dfn[x] = ++dfntot;
	for(int i = 0; i < (int)g[x].size(); i++)
	{
		int v = g[x][i]; 
		if(v == fa) continue;
		dfs(v,x,dep + 1,xg);
		if(xg) siz[x] += siz[v];
	}
	return;
}
void dfs2(int x,int fa)
{
	if(!Ok) return;
	Link.push_back(x);
	for(int i = 0; i < (int)g[x].size(); i++)
	{
		int v = g[x][i]; if(v == fa) continue;
		if(dfn[v] <= dfn[R] && dfn[R] <= dfn[v] + siz[v] - 1) // R in T_v
		{
			dfs2(v,x);
		}
		else if(siz[v] > 1) 
		{
			Ok = 0; return;
		}
		else S[x].push_back(v);
	}
	return;
}
void solve(void)
{
	int tot = 0;
	int L = (int)Link.size();
	if(L % 2 == 0)
	{
		for(int i = 0; i < L; i += 2)
		{
			p[++tot] = Link[i];
//			if(i == L - 1) break;
			for(int v : S[Link[i + 1]]) p[++tot] = v;
		}
//		p[++tot] = L - 1;
//		for(int v : S[Link[L - 1]]) p[++tot] = v;
		for(int i = L - 1; i >= 0; i -= 2)
		{
			p[++tot] = Link[i];
			for(int v : S[Link[i - 1]]) p[++tot] = v;
		}
	}
	else 
	{
		for(int i = 0; i < L; i += 2)
		{
			p[++tot] = Link[i];
			if(i + 1 < L) 
			{
				for(int v : S[Link[i + 1]]) p[++tot] = v;
			}
		}
		for(int i = L - 2; i >= 0; i -= 2)
		{
			p[++tot] = Link[i];
			if(i - 1 >= 0)
			{
				for(int v : S[Link[i - 1]]) p[++tot] = v;
			}
		}
	}
	return;
}
int main(void)
{
	scanf("%d",&n);
	for(int i = 1; i < n; i++)
	{
		int u,v; scanf("%d%d",&u,&v);
		g[u].push_back(v),g[v].push_back(u);
	}
	y = 0, maxl = 0; 
	dfs(1,0,0); L = y,maxl = 0;
//	printf("y = %d, maxl = %d\n",y,maxl);
	dfs(L,0,0,1); R = y;
//	printf("L = %d,R = %d\n",L,R);
	dfs2(L,0);
//	printf("Link : \n");
//	for(int x : Link) printf("%d ",x);
//	printf("\n");
	if(!Ok) 
	{
		printf("No\n");
		return 0;
	}
	solve();
	printf("Yes\n");
	for(int i = 1; i <= n; i++) printf("%d ",p[i]);
	return 0;
}